package com.mid;

import java.util.*;

/**
 * Created by Lxk on 2020/1/23.
 */
public class Solution18 {


    public List<List<Integer>> fourSum(int[] nums, int target) {
        Map<String, Boolean> flag = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> numDatas = new ArrayList<>();
        for (Integer num : nums) {
            numDatas.add(num);
        }
        Collections.sort(numDatas);
        for (int i = 0; i < numDatas.size() - 1; i++) {
            for (int k = i + 1; k < numDatas.size(); k++) {
                int curTarget = target - (numDatas.get(i) + numDatas.get(k));
                //left表示左边位置，right表示右边位置
                int left = k + 1, right = numDatas.size() - 1;
                while (left < right && right < numDatas.size()) {
                    int curSum = numDatas.get(left) + numDatas.get(right);
                    if (curTarget > curSum) {
                        left++;
                    } else if (curTarget < curSum) {
                        right--;
                    } else {
                        StringBuffer sb = new StringBuffer();
                        sb.append(numDatas.get(i)).append(",").append(numDatas.get(k)).append(",")
                          .append(numDatas.get(left)).append(",").append(numDatas.get(right));
                        if (!flag.keySet().contains(sb.toString())) {
                            List<Integer> curRes = new ArrayList<>();
                            curRes.add(numDatas.get(i));
                            curRes.add(numDatas.get(k));
                            curRes.add(numDatas.get(left));
                            curRes.add(numDatas.get(right));
                            res.add(curRes);
                            flag.put(sb.toString(), true);
                        }
                        left++;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1, 0, -1, 0, -2, 2};
        Solution18 solution18 = new Solution18();
        System.out.println(solution18.fourSum(arr, 0));
    }

}
